package Hot100.leetcode.editor.cn.code.二分;

import java.util.Arrays;

//Java：咒语和药水的成功对数
public class SuccessfulPairsOfSpellsAndPotions {
    public static void main(String[] args) {
        Solution solution = new SuccessfulPairsOfSpellsAndPotions().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] successfulPairs(int[] spells, int[] potions, long success) {
            Arrays.sort(potions);
            for (int i = 0; i < spells.length; i++) {
                long target = (success - 1) / spells[i];
                if (target < potions[potions.length - 1]) {
                    // 这样写每次二分就只用比两个 int 的大小，避免把 potions 中的元素转成 long 比较
                    spells[i] = potions.length - upperBound(potions, (int) target);
                } else {
                    spells[i] = 0;
                }
            }
            return spells;

        }
        //左闭右闭区间
        private int upperBound(int[] nums, int left, int right, int target) {
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
        //返回数组中第一个大于target的元素索引  左闭右开区间
        private int upperBound(int[] nums, int target) {
            int left = 0;
            int right = nums.length;
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (nums[mid] > target) {
                    right = mid;//我们要的就是大于target所以赋值给right
                }
                else {
                    left = mid + 1;
                }
            }
            return right;
        }



//        二分
//        public static int binarySearch(int[] nums, int target) {
//            int left = 0;
//            int right = nums.length - 1;
//
//            while (left <= right) {
//                int mid = left + (right - left) / 2;
//
//                if (nums[mid] == target) {
//                    return mid; // 找到目标值
//                } else if (nums[mid] < target) {
//                    left = mid + 1; // 在右半部分继续查找
//                } else {
//                    right = mid - 1; // 在左半部分继续查找
//                }
//            }
//
//            return -1; // 未找到目标值
//        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
